//
// Created by hay boy on 2022/6/28.
//

#ifndef ALGORITHMS_TRAINREARRANGEMENT_H
#define ALGORITHMS_TRAINREARRANGEMENT_H
#include "../stack/ArrayStack.h"
ArrayStack<int>* track;
int numberOfCars;
int numberOfTracks;
int smallestCar;
int itsTrack;
void outputFromHoldingTrack();//O（numberOfTracks)
bool putInHoldingTrack(int c);//O(numberOfTracks)
bool railroad(int inputOrder[],int theNumberOfCars,int theNumberOfTracks){//O(numberOfTracks * numberOfCars)
    numberOfCars = theNumberOfCars;
    numberOfTracks = theNumberOfTracks;
    track = new ArrayStack<int>[numberOfTracks+1];
    int nextCarToOutput = 1;
    smallestCar = numberOfCars + 1;
    for(int i = 1;i<=numberOfCars;i++){
        if(inputOrder[i]==nextCarToOutput){
            cout<<"Move car "<<inputOrder[i]<<" from input track to output track"<<endl;
            nextCarToOutput++;
            while(smallestCar==nextCarToOutput){
                outputFromHoldingTrack();
                nextCarToOutput++;
            }
        }else{
            if(!putInHoldingTrack(inputOrder[i]))
                return false;
        }
    }
    return false;
}
void outputFromHoldingTrack(){
    track[itsTrack].pop();
    cout<<"Move car "<<smallestCar<<" from holding "<<"track "<<itsTrack<<" to output track"<<endl;
    smallestCar = numberOfCars + 2;
    for(int i = 1;i <= numberOfTracks; i++){
        if(!track[i].empty()&&(track[i].top()<smallestCar)){
            smallestCar = track[i].top();
            itsTrack = i;
        }
    }
}
bool putInHoldingTrack(int c){
    int bestTrack = 0;
    int bestTop = numberOfCars + 1;
    for(int i = 1;i <= numberOfTracks;i++){
        if(!track[i].empty()){
            int topCar = track[i].top();
            if(c<topCar&&topCar<bestTop){
                bestTop = topCar;
                bestTrack = i;
            }
        }else if(bestTrack == 0)
            bestTrack = i;
    }
    if(bestTrack == 0){
        return false;
    }
    track[bestTrack].push(c);
    cout<<"Move car "<<c<<" from input track "<<"to holding track "<<bestTrack
    <<endl;
    if(c<smallestCar){
        smallestCar = c;
        itsTrack = bestTrack;
    }
    return true;
}
#endif //ALGORITHMS_TRAINREARRANGEMENT_H
